//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

  struct ListNode {
      int val;
      struct ListNode *next;
  };
#include <cstddef>
  //方法一计算链表长度
struct ListNode* removeNthFromEnd1(struct ListNode* head, int n)
{
    if (head == NULL)
    {
        return NULL;
    }

    struct ListNode* cur = head;
    struct ListNode* prev = head;

    int k = 0;
    while (cur)
    {
        cur = cur->next;
        k++;
    }
    if (k == 1)
    {
        return NULL;
    }
    cur = head;
    int i = 1;
    prev = cur;;

    while (i < k - n + 1)
    {
        prev = cur;
        cur = cur->next;
        i++;
    }
    if (n == k)
    {
        return cur->next;
    }
    if (cur)
    {
        prev->next = cur->next;
        cur->next = NULL;
        free(cur);
    }
    else
    {
        prev->next = NULL;
    }

    return head;


}
//方法二   双指针

struct ListNode* removeNthFromEnd2(struct ListNode* head, int n)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    phead->val = 0;
    phead->next = head;
    struct ListNode* cur = head;
    struct ListNode* prev = phead;


    for (int i = 0; i < n; ++i)
    {
        cur = cur->next;
    }
    while (cur)
    {
        cur = cur->next;
        prev = prev->next;
    }

    struct ListNode* del = prev->next;
    prev->next = del->next;
    free(del);
    del = NULL;
    struct ListNode* newhead = phead->next;
    free(phead);
    return newhead;
}